//
// Unihan Input Method
//
// Copyright © 2002-2007 Sun Wah Linux Ltd.
//
//
// This library is free software; you can redistribute it and/or modify
// it under the terms of the GNU Lesser General Public License as
// published by the Free Software Foundation; either version 2.1 of the
// License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307
// USA
//
// $Id: candidates.c 757 2007-05-10 08:19:31Z roger $
//

/* FILE : candidates.c */
#ifdef HAVE_CONFIG_H
# include <config.h>
#endif

#include <SWTable.h>
#include <unihan_im.h>
#include <unihan_im_keycodes.h>

#include <stdio.h>
#include <string.h>

#include "im_config.h"
#include "candidates.h"
#include "preprocess.h"
#include "utils.h"

static void node_find_candidates(Node *node,
			TableConfig *config,
			BaseTable *base_table,
			Adjuster *adjuster,
			PhraseTableList *phrase_table_list);

static void snode_find_candidates(SNode *node,
			TableConfig *config,
			BaseTable *base_table,
			Adjuster *adjuster,
			PhraseTableList *phrase_table_list,
			int num_table);

static void base_find_candidates(Candidate *candidate,
		BaseTable *base_table,
		char *preedit,
		int preeditLen);

static void phrase_find_candidates(Candidate *candidate,
		BaseTable *base_table,
		PhraseTableList *phrase_table,
		char *preedit,
		int preeditLen);

static const char *
node_get_candidates_by_candID(Node *node,
			int id,
			BaseTable *base_table,
			PhraseTableList *phrase_table_list);

static void destroy_input_list(InputList *input_list);
static Frequence node_get_frq_by_candID(Node *node,
				BaseTable *base_table,
				Adjuster *adjuster,
				int id);

void
node_destroy(Node *node)
{
#if DEBUG
	fprintf(stderr, "table : destroy a candidate node\n");
#endif
	int i;

	for(i=0; i<node->numSNode; i++) {
		free(node->sNode[i].candidates);
	}

	free(node->sNode);
	free(node->freqList);
	node->sNode = NULL;
	node->freqList = NULL;
	node->prev = NULL;
	node->next = NULL;
	node->punc = 0;
	node->defaultCandLen = 0;
	if (node->freqList) {
		free(node->freqList);
		node->freqList = NULL;
	}
}

int
node_stacked(Node *node,
		IMKeyEvent *kev,
		TableConfig *config,
		BaseTable *base_table,
		Adjuster *adjuster,
		PhraseTableList *phrase_table_list)
{
#if DEBUG
	fprintf(stderr, "table : stacked a candidate node\n");
#endif
	InputList *input_list = NULL;
	Node *next = node->next;
	int i;

	input_list = pp_get_input_list(base_table, node, config, kev);

	if (!node->inputList) {
		node->inputList = node->lastInputList = input_list;
		input_list->next = input_list->prev = NULL;
		node->numSNode = input_list->num;
	} else {
		node->lastInputList->next = input_list;
		input_list->prev = node->lastInputList;
		node->lastInputList = input_list;
		node->numSNode *= input_list->num;
	}

	if (!node->sNode) {
		node->numSNode = input_list->num;
		node->sNode = (SNode *)calloc(sizeof(SNode), node->numSNode);
		for(i=0; i<input_list->num; i++) {
			strcpy(node->sNode[i].preedit,
					input_list->stringList[i]);
			node->sNode[i].preeditLen = strlen(
					input_list->stringList[i]);
		}
	} else {
		if (input_list->num == 1) {
			int i;
			for(i=0; i<node->numSNode; i++) {
				strcat(node->sNode[i].preedit,
					input_list->stringList[0]);
				node->sNode[i].preeditLen += strlen(
					input_list->stringList[0]);
			}
		} else if (input_list->num > 1) {
			int num_orig_s_node = node->numSNode;
			SNode *s_node;
			int i,j;
			node->sNode = (SNode *)realloc(node->sNode,
					sizeof(SNode) * input_list->num);
			for(i=0; i<input_list->num; i++) {
				s_node = &(node->sNode[num_orig_s_node*(i+1)]);
				memcpy(s_node, node->sNode,
					sizeof(SNode) * num_orig_s_node);
				for(j=0; j<num_orig_s_node; j++) {
					strcat(node->sNode[num_orig_s_node*i+j].preedit,
							input_list->stringList[i]);
					node->sNode[num_orig_s_node*i+j].preeditLen +=
							strlen(input_list->stringList[i]);
				}
			}
		}
	}
	node_find_candidates(node,
			config,
			base_table,
			adjuster,
			phrase_table_list);
	if (node->numTotalCands == 0) {
#if DEBUG
		fprintf(stderr, "table : find candidates failed!\n");
#endif
		node_pop(node,
			config,
			base_table,
			adjuster,
			phrase_table_list);
		return FALSE;
	}
	node->page = 0;
	node->luCurrCandOffset = 0;
	node->defaultCandLen = strlen(node_get_selected_candidates(node,
							base_table,
							phrase_table_list));
	return TRUE;
}

void
node_pop(Node *node,
		TableConfig *config,
		BaseTable *base_table,
		Adjuster *adjuster,
		PhraseTableList *phrase_table_list)
{
#if DEBUG
	fprintf(stderr, "table : candidate node pop\n");
#endif
	InputList *input_list = node->lastInputList;
	int num = node->numSNode / input_list->num;
	int i;

	if (node->lastInputList)
		node->lastInputList = node->lastInputList->prev;

	if (num < node->numSNode)
		node->sNode = (SNode *)realloc(node->sNode, num*sizeof(SNode));
	
	for (i=0; i<num; i++) {
		node->sNode[i].preeditLen -= strlen(input_list->stringList[0]);
		node->sNode[i].preedit[node->sNode[i].preeditLen] = 0x0;
	}

	node_find_candidates(node,
			config,
			base_table,
			adjuster,
			phrase_table_list);
	//node_preedit_pop(node);
}

int
node_kick(Node *node, IMKeyEvent *kev, TableConfig *config)
{
#if DEBUG
	fprintf(stderr, "table : kick a node\n");
#endif
	int num_sel;

	num_sel = node->numTotalCands - node->page*config->pageSize;
	if (num_sel >= config->pageSize)
		num_sel = config->pageSize;
	else
		num_sel = node->numTotalCands % config->pageSize;
	if (!num_sel)
		num_sel = config->pageSize;

	if (kev->keyCode >= IM_VK_1 && kev->keyCode <= IM_VK_9) {
		if (kev->keyCode - IM_VK_0 <= num_sel) {
			node->luCurrCandOffset = kev->keyCode - IM_VK_1;
			node->kicked = 1;
			node->editing = 1;
			return TRUE;
		} else
			return FALSE;
	}

	node->kicked = 1;
	node->editing = 1;
	//FIXME : auto fill preedit.
	return TRUE;
}

int
node_page_up(Node *node, TableConfig *config)
{
	if (node->page > 0) {
		node->page--;
		return TRUE;
	} else {
		return FALSE;
	}
}

int
node_page_down(Node *node, TableConfig *config)
{
	int page_size = config->pageSize;
	int num_total_page;

	num_total_page = node->numTotalCands / page_size;
	if (node->numTotalCands % page_size)
		num_total_page++;

	if (node->page < num_total_page - 1) {
		node->page++;
		return TRUE;
	} else {
		return FALSE;
	}
}

int
node_sel_up(Node *node, TableConfig *config)
{
	int num_sel;

	num_sel = node->numTotalCands - node->page*config->pageSize;
	if (num_sel >= config->pageSize)
		num_sel = config->pageSize;
	else
		num_sel = node->numTotalCands % config->pageSize;
	if (!num_sel)
		num_sel = config->pageSize;
	
	if (node->luCurrCandOffset > 0) {
		node->luCurrCandOffset--;
	} else {
		node->luCurrCandOffset = num_sel;
	}
	return TRUE;
}

int
node_sel_down(Node *node, TableConfig *config)
{
	int num_sel;

	num_sel = node->numTotalCands - node->page*config->pageSize;
	if (num_sel >= config->pageSize)
		num_sel = config->pageSize;
	else
		num_sel = node->numTotalCands % config->pageSize;
	if (!num_sel)
		num_sel = config->pageSize;
	
	if (node->luCurrCandOffset < num_sel) {
		node->luCurrCandOffset++;
	} else {
		node->luCurrCandOffset = 0;
	}
	return TRUE;
}

static void
node_find_candidates(Node *node,
		TableConfig *config,
		BaseTable *base_table,
		Adjuster *adjuster,
		PhraseTableList *phrase_table_list)
{
#if DEBUG
	fprintf(stderr, "table : node find candidates\n");
#endif
	SNode *s_node = node->sNode;
	int i;
	int num_table = 1;

	PhraseTableList *list = phrase_table_list;

	while(list) {
		num_table++;
		list = list->next;
	};

	node->numTotalCands = 0;

	for(i=0; i<node->numSNode; i++) {
		snode_find_candidates(&(s_node[i]),
				config,
				base_table,
				adjuster,
				phrase_table_list,
				num_table);
		node->numTotalCands += s_node[i].numCands;
	}

#if DEBUG
	fprintf(stderr, "table : node get total candidates %d\n",
			node->numTotalCands);
#endif
	node->freqList = (int *)realloc(node->freqList,
			sizeof(int) * node->numTotalCands);
	for(i=0; i<node->numTotalCands; i++) {
		node->freqList[i] = i;
	}

	if (config->FreqMode) {
		int j;

		for(i=node->numTotalCands; i>1; i--) {
			for(j=0; j<i-1; j++) {
				Frequence frq1, frq2;
				int id1, index1;
				int id2, index2;
				Frequence frqtmp;

				id1 = node->freqList[j];
				frq1 = node_get_frq_by_candID(node,
						base_table,
						adjuster,
						id1);

				id2 = node->freqList[j+1];
				frq2 = node_get_frq_by_candID(node,
						base_table,
						adjuster,
						id2);

				if (frq1 < frq2) {
					frqtmp = node->freqList[j];
					node->freqList[j] = node->freqList[j+1];
					node->freqList[j+1] = frqtmp;
				}
			}
		}
	}

}

static void
snode_find_candidates(SNode *s_node,
		TableConfig *config,
		BaseTable *base_table,
		Adjuster *adjuster,
		PhraseTableList *phrase_table_list,
		int num_table)
{
#if DEBUG
	fprintf(stderr, "table : SNode find candidates\n");
#endif
	int i;
	PhraseTableList *list = phrase_table_list;

	if (s_node->preeditLen == 0) {
		s_node->numCands = 0;
		return;
	}

	s_node->candidates = (Candidate *)realloc(s_node->candidates,
			sizeof(Candidate) * num_table);
	s_node->numCands = 0;

	base_find_candidates(&(s_node->candidates[0]),
			base_table,
			s_node->preedit,
			s_node->preeditLen);
	s_node->numCands = s_node->candidates[0].numCands;
}

int
snode_phrase_search(SNode *s_nodes,
		int num_s_node,
		BaseTable *base_table,
		PhraseTableList *phrase_table_list,
		int num_phrase_table)
{
#if DEBUG
	fprintf(stderr, "table : snode phrase search\n");
#endif
	int i,j;
	int num_cands = 0;
	PhraseTableList *phrase_table = phrase_table_list;

	for(i=0; i<num_s_node; i++) {
		phrase_table = phrase_table_list;
		s_nodes[i].candidates = (Candidate *)malloc(sizeof(Candidate)*
				num_phrase_table);
		memset(s_nodes[i].candidates, 0, sizeof(Candidate)*num_phrase_table);
		for (j=0; j<num_phrase_table, phrase_table; j++) {
			phrase_find_candidates(&(s_nodes[i].candidates[j]),
					base_table,
					phrase_table,
					s_nodes[i].preedit,
					s_nodes[i].preeditLen);
			s_nodes[i].numCands +=s_nodes[i].candidates[j].numCands;
			phrase_table = phrase_table->next;
		}
		num_cands += s_nodes[i].numCands;
	}
	if (num_cands) {
		return TRUE;
	} else {
#if DEBUG
		fprintf(stderr, "table : snode phrase search failed\n");
#endif
		return FALSE;
	}
}

/* index : node position in phrase */
void
node_select_cand_from_snodes(Node *node,
			TableConfig *config,
			BaseTable *base_table,
			PhraseTableList *phrase_table_list,
			int num_phrase_table,
			SNode *s_nodes,
			int num_s_node,
			int index)
{
#if DEBUG
	fprintf(stderr, "table : node select candidate from snodes\n");
#endif
	int i,j;
	char *phrase = NULL;
	const unsigned char *cand_char;
	CN_IDX cand_rs_idx;
	int check_list_index;
	PhraseTableList *phrase_table;

	for (i=0; i<num_s_node; i++) {
		phrase_table = phrase_table_list;
		if (s_nodes[i].numCands) {
			for (j=0; j<num_phrase_table, phrase_table; j++) {
				if (s_nodes[i].candidates[j].numCands) {
					phrase = phrase_table->charData +
						phrase_table->simCheckListIndex[
							s_nodes[i].candidates[j].lowIdx
							].charOff;
					break;
				}
				phrase_table = phrase_table->next;
			}
		}
	}

	if (phrase) {
#if DEBUG
		fprintf(stderr, "table : get phrase %s\n", phrase);
#endif
		cand_char = phrase;
		for(i=0; i<index && *cand_char; i++) {
			cand_char = utf8_next_char(cand_char);
		}
		if (*cand_char) {
			const unsigned char *tmp;
			char *preedit;
			int char_off;
			int idx;
			tmp = utf8_next_char(cand_char);
			UTF_CN_TO_INT_IDX(cand_rs_idx, cand_char);
			check_list_index = base_table->rsTable[cand_rs_idx - base_table->header->minChar];

			char_off = base_table->checkListIndex[check_list_index].charOff;
			for(idx=0; idx<node->numTotalCands; idx++) {
				if (base_table->checkListIndex[
						node->sNode[0].candidates[0].lowIdx +
						node->freqList[idx]
						].charOff == char_off) {
					break;
				}
			}
			if (idx == node->numTotalCands)
				idx = 0;
			node->page = idx / config->pageSize;
			node->luCurrCandOffset = idx % config->pageSize;
		}
	}
	return;
}

/* Now I use strlen() to cmp which is most long cand ,so only for CN chars*/
int
node_is_last_in_phrase(Node *node,
			PhraseTableList *phrase_table_list,
			int num_phrase_table,
			SNode *s_nodes,
			int num_s_node)
{
#if DEBUG
	fprintf(stderr, "table : node is last in phrase\n");
#endif
	int i;
	int s_node_idx=0, table_idx=0;

	/*for (i=0; i<num_s_node; i++) {
	}*/
	return FALSE;
}

static void
base_find_candidates(Candidate *candidate,
		BaseTable *base_table,
		char *preedit,
		int preeditLen)
{
#if DEBUG
	fprintf(stderr, "table : base table find candidates\n");
#endif
	int low, high, exactIdx, i;
	CheckListIndex *base_index = base_table->checkListIndex;
	CheckListIndex *cli = NULL;

	low = base_table->fastIdx[idx(preedit[0])].offset;
	high = base_table->fastIdx[idx(preedit[0])+1].offset - 1;
	i = (low + high) / 2;

	/* binary search */
	while (preeditLen > 1) {
		int cmp;

		if (high < low) {
			candidate->numExactCands =
				candidate->highIdx =
				candidate->lowIdx =
				candidate->exactIdx = -1;
			candidate->numCands = 0;
			return;
		}

		i = (low + high)/2;

		cli = &(base_index[i]);
		cmp = strncmp(preedit+1,
			base_table->keyData + (cli->keyOff)+1,
			preeditLen-1);
		if (cmp < 0)
			high = i - 1;
		else if (cmp > 0)
			low = i + 1;
		else // cmp == 0!!! found!
			break;
	}

	// find the real upper and lower ranges
	low = i - 1;
	high = i + 1;
	while (low >= 0) {
		cli = &(base_index[low]);
		int cmp = strncmp(preedit,
				base_table->keyData+(cli->keyOff),
				preeditLen);
		if (cmp != 0) // found start of range
			break;
		--low;
	}
	++low;
	while (high < base_table->header->numChar) {
		cli = &(base_index[high]);
		int cmp = strncmp(preedit,
				base_table->keyData+(cli->keyOff),
				preeditLen);
		if (cmp != 0)
			break;
		++high;
	}

	// find how many are exact matches
	//base_index = &(base_index[low]);
	if (preeditLen < strlen(base_table->keyData + base_index->keyOff)) {
		exactIdx = low + 1;
	} else {
		exactIdx = low + 1;
		while (exactIdx < high) {
			cli = &(base_index[exactIdx]);
			if (*(base_table->keyData +
					cli->keyOff+preeditLen) != 0)
				break;
			++exactIdx;
		}
	}

	candidate->lowIdx = low;
	candidate->highIdx = high;
	candidate->exactIdx = exactIdx;
	candidate->numExactCands = exactIdx - low;
	//if (dd->hints & SHOW_AS_U_GO)
		candidate->numCands = high - low;
	//else
	//	ds->numCands = ds->numExactCands;
	//if (candFactory->word)
	//	ds->numCands++;
	return;
}

static void
phrase_find_candidates(Candidate *candidate,
		BaseTable *base_table,
		PhraseTableList *phrase_table,
		char *preedit,
		int preeditLen)
{
#if DEBUG
	fprintf(stderr, "table : phrase table find candidates preedit : %s\n", preedit);
#endif
	int low, high, exactIdx, i;
	SimCheckListIndex *phrase_index = phrase_table->simCheckListIndex;
	SimCheckListIndex *scli = NULL;

	low = phrase_table->fastIdx[idx(preedit[0])].offset;
	high = phrase_table->fastIdx[idx(preedit[0])+1].offset - 1;
	i = (low + high)/2;

	// binary search
	while (preeditLen > 1) {
		int cmp;

		if (high < low) {
			candidate->numExactCands =
				candidate->highIdx =
				candidate->lowIdx =
				candidate->exactIdx = -1;
			candidate->numCands = 0;
			return;
		}

		i = (low + high)/2;

		scli = &(phrase_index[i]);
		cmp = strncmp(preedit+1,
				phrase_table->keyData+(scli->keyOff)+1,
				preeditLen-1);
		if (cmp < 0) {
			high = i - 1;
		} else if (cmp > 0) {
			low = i + 1;
		} else {// cmp == 0!!! found!
			break;
		}
        }

	// find the real upper and lower ranges
	low = i - 1;
	high = i + 1;
	while (low >= 0) {
		scli= &(phrase_index[low]);
		int cmp = strncmp(preedit,
			phrase_table->keyData+(scli->keyOff),
			preeditLen);
		if (cmp != 0) // found start of range
			break;
		--low;
	}
	++low;
	while (high < phrase_table->header->numCharList) {
		scli = &(phrase_index[high]);
		int cmp = strncmp(preedit,
			phrase_table->keyData+(scli->keyOff),
			preeditLen);
		if (cmp != 0)
			break;
		++high;
	}

	// find how many are exact matches
	//phrase_index = &(phrase_table->simCheckListIndex[low]);
	if (preeditLen < strlen(phrase_table->keyData+phrase_index->keyOff)) {
		exactIdx = low + 1;
	} else {
		exactIdx = low + 1;
		while (exactIdx < high) {
			scli = &(phrase_index[exactIdx]);
			if (*(phrase_table->keyData +
					scli->keyOff+
					preeditLen) != 0)
				break;
			++exactIdx;
		}
	}

	candidate->lowIdx = low;
	candidate->highIdx = high;
	candidate->exactIdx = exactIdx;
	candidate->numExactCands = exactIdx - low;
	//if (dd->hints & SHOW_AS_U_GO)
		candidate->numCands = high - low;
	//else
	//	ds->numCands = ds->numExactCands;
	//if (candFactory->word)
	//	ds->numCands++;
	return;
}

const char *
node_get_preedit(Node *node)
{
	const char *preedit = node->sNode->preedit;
	return preedit;
}

int
node_preedit_len(Node *node)
{
	return node->sNode[0].preeditLen;
}

const char *
node_get_candidates(Node *node,
		int index,
		BaseTable *base_table,
		PhraseTableList *phrase_table_list)
{
	int id = node->freqList[index];
	const char *cand_string = node_get_candidates_by_candID(node,
							id,
							base_table,
							phrase_table_list);
	return cand_string;
}

static const char *
node_get_candidates_by_candID(Node *node,
			int id,
			BaseTable *base_table,
			PhraseTableList *phrase_table_list)
{
	//int offset;
	//int num_table = 1;
	//PhraseTableList *phrase_table = phrase_table_list;

	//if (base_table)
	//	num_table++;

	/*while (phrase_table) {
		num_table++;
		phrase_table = phrase_table->next;
	}*/

	SNode *s_node = node->sNode;
	const char *cand_string;
	int offset;

	offset = base_table->checkListIndex[
				s_node[0].candidates[0].lowIdx + 
				id
				].charOff;
	cand_string = base_table->charData + offset;

	return cand_string;
}

static void
clear_input_list(InputList *input_list)
{
	int i;

	for(i=0; i<input_list->num; i++) {
		free(input_list->stringList[i]);
	}

	free(input_list->stringList);
}

const char *
node_get_selected_candidates(Node *node,
			BaseTable *base_table,
			PhraseTableList *phrase_table_list)
{
#if 0
	fprintf(stderr, "table : node get selected candidates\n");
#endif
	SNode *s_node = node->sNode;
	const char *cand_string;
	int offset;
	int id, idx;

	if (node->punc) {
		return node->puncString;
	}

	idx = node->page * 9 + node->luCurrCandOffset;
	id = node->freqList[idx];
	offset = base_table->checkListIndex[
				s_node[0].candidates[0].lowIdx + 
				id
				].charOff;
	cand_string = base_table->charData + offset;

	return cand_string;
}

static Frequence
node_get_frq_by_candID(Node *node,
		BaseTable *base_table,
		Adjuster *adjuster,
		int id)
{
	SNode *s_node = node->sNode;
	int offset;

	offset = base_table->checkListIndex[
				s_node[0].candidates[0].lowIdx + 
				id
				].frqOff;
	return adjuster->freqTable[offset];
}

void
node_post_freq(Node *node,
		BaseTable *base_table,
		Adjuster *adjuster,
		TableConfig *config)
{
#if DEBUG
	fprintf(stderr, "table : node post frequence\n");
#endif
	SNode *s_node = node->sNode;
	MaxFrequence max_freq;
	int offset;
	int highIdx;
	int selected = node->page * config->pageSize + node->luCurrCandOffset;
	int id = node->freqList[selected];
	Frequence freq;

	if (selected == 0) {
		return;
	}

	offset = base_table->checkListIndex[
				s_node[0].candidates[0].lowIdx +
				id
				].maxFrqOff;
	max_freq = adjuster->maxFreqTable[offset];

	offset = base_table->checkListIndex[
				s_node[0].candidates[0].lowIdx + 
				id
				].frqOff;

	freq = adjuster->freqTable[offset] + 1;

	highIdx = selected -1;

	while (highIdx) {
		int highId = node->freqList[highIdx];
		int highOffset = base_table->checkListIndex[
						s_node[0].candidates[0].lowIdx +
						highId
						].frqOff;
		if (adjuster->freqTable[highOffset])
			adjuster->freqTable[highOffset]--;
		highIdx--;
	}

	if (freq > max_freq)
		freq = max_freq;
	adjuster->freqTable[offset] = freq;
}

void
node_set_first_cand(Node *node,
		int check_list_index,
		BaseTable *base_table,
		TableConfig *config)
{
	int i,j;
	int id = 0;

	for (i=0; i<node->numTotalCands; i++) {
		if (node->sNode->candidates[0].lowIdx +
				node->freqList[i]
				== check_list_index) {
			id = node->freqList[i];
			break;
		}
	}

	if (i < node->numTotalCands) {
		for (j=i-1; j>=0; j--) {
			node->freqList[j+1] = node->freqList[j];
		}
		node->freqList[0] = id;
	}
}

// vi:ts=4:nowrap:cin:expandtab
